The ATM (Asynchronous Transfer Mode) protocol is an example of a packet switched network protocol that supports a plurality of communications services such as voice, video, and data. Information is transmitted over an ATM network using fixed-sized data packets called cells. Routing information that is used to direct a cell to its destination is contained in the cell's header. The cell routing information, which is determined at call setup time, specifies a fixed route through a switching network. Depending on the particular fixed route defined through a network, a cell may travel through a series of ATM switches before arriving at its destination.
As ATM networks become common and are used as office networks, the availability of small scaleable switches becomes increasingly desirable. ATM switches that are readily scaleable support a number of different configurations at once. Also, a switch that is readily scaleable operates efficiently when its port capacity is partially utilized (or populated). For example, a switch that is readily scaleable can be used to deploy multiple versions of the switch using identical printed circuit boards, thereby reducing manufacturing and development costs. It would, therefore, be advantageous for an ATM switch to operate efficiently using identical circuit boards when the number of ports vary between configurations. Also, it would be desirable to provide an ATM switch that automatically determines while in operation how many ports of the ATM switch are in use during a switch cycle.
In an office environment these small, scaleable switches can be used as "ATM extension cords" to connect office equipment to larger and more central switches via a single physical connection. When used in this manner small switches do not necessarily need to support the throughput levels required by a central switch. It is, therefore, desirable that this small scaleable switch architecture operate efficiently while operating with limited switching bandwidth. Small scaleable switches with limited bandwidth switching networks have a set of output ports to which the switching network can transmit a limited number of cells each switch cycle. In general, a switch with limited switching bandwidth operates with a throughput that is less than the aggregate maximum link rate at which the input ports can theoretically operate. In addition to operating with limited bandwidth, it is desirable to have a small switch architecture that ensures that cell loss is infrequent, while supporting traffic priorities and multicast operations.
A switch that operates with a limited bandwidth may be "blocking" because such a switch is unable to generate all possible one-to-one input port to output port mappings in a single switch cycle. In a switch that may be blocking, input buffering is required in order to avoid cell loss. Input buffering is also desirable even in the presence of output buffering. For example, input buffers are necessary when output buffers are incapable of queuing the maximum number of cells that might be destined for any particular output buffer during any single switch cycle. As described in U.S. Pat. No. 5,305,311, the combination of input and output buffering provides an effective method for limiting the output buffer bandwidth required to achieve loss-less switching.
It is well known, however, that switches that use input queuing and deliver one cell to an output port per switch cycle suffer from head of queue blocking. Generally, head of queue blocking will cause a gross degradation in throughput. U.S. Pat. No. 5,305,311, discloses the notion of speeding up each output port by a factor of "k" (e.g. k=2) each switch cycle to minimize head of queue blocking. This speedup of "k" per output port increases throughput from approximately 58% for k=1 (purely input queued) to approximately 89% for k=2 and nearly 100% for k=4 and above.
One resource that limits the amount of bandwidth available when designing a small scaleable switch is the number of pins available on integrated circuits used to build the switch. For example, in a bus-based switching network, the width of the bus limits the bandwidth of the bus. Besides the bus width, the bandwidth for a bus-based switching network is limited by the clock speed of the switch, and the number of ports on the switch. Consequently, in a small scaleable switch with a bus based switching network, the bandwidth at which the switch can operate is often constrained by the number of wires that link input and output ports of the switching network.